package Array;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

// 15.三数之和（LeetCode）
/**
 * 题目条件 ：
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
 * 同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
 * 你返回所有和为 0 且不重复的三元组。
 */
public class ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new LinkedList<List<Integer>>();
        // 定义一个List集合去存储三元组（其中三元组也是用List集合去存储）
        int length = nums.length;
        if(length >= 3) {   // 数组必须要大于或者等于3，才能存在三个数
            // 1.对整数数组进行排序（从小到大） ===> 时间复杂度：O（nlogn）;
            Arrays.sort(nums);
            int i = 0;
            // 2.首先，固定住数组中的一个元素；然后就是对于两个数字求和的做法 (双指针思想)
            while(i < length - 2) {
                twoSum(i, nums, lists);
                /**
                 *  需要去除重复的二元组(如何去除重复的二元组)
                 *  去重的核心思想 ：即，通过下标的增加 ===> 跳过重复的数字;
                  */
                int temp = nums[i];
                while (nums[i] == temp && i < length - 2){
                    i++;
                }
            }

        }
        return lists;
    }

    /**
     * 遍历整个数组，获取两个数和为定值的List集合
     * @param i
     * @param nums
     * @param lists
     */
    private void twoSum(int i,int[] nums,List<List<Integer>> lists){
        int leftPointer = i + 1;  // 左指针指向所固定的元素后的第一个元素
        int rightPointer = nums.length - 1;  // 右指针指向排序数组的最后一个元素
        while(leftPointer < rightPointer) {
            // 由于此处使用双指针遍历整个整数数组，所需要的时间复杂度：O（n*n）;
            if (nums[leftPointer] + nums[rightPointer] + nums[i] > 0) { // 右指针左移
                rightPointer -= 1;
            } else if (nums[leftPointer] + nums[rightPointer] + nums[i] < 0) { //左指针右移
                leftPointer += 1;
            } else {
                lists.add(Arrays.asList(nums[leftPointer], nums[rightPointer], nums[i]));
                /**
                 * 此处向List集合中存储二元组之后，需要进行指针的移动
                 * 去重的核心思想 ：即，通过下标的增加 ===> 跳过重复的数字;
                 * 1.左指针右移 ：即，其的去重方式为：固定住右指针，左指针向右移，直至左指针所获取的值，与左指针最初指向的值不同
                 * 2.右指针左移 ：即，其的去重方式为：固定住左指针，右指针向左移，直至右指针所获取的值，与右指针最初指向的值不同
                 */
                int temp = nums[leftPointer]; // 使用临时变量来存储左指针所指向的初始值
                while(nums[leftPointer] == temp && leftPointer < rightPointer){
                    leftPointer++;
                }
            }
        }
    }
}
